#include <iostream>
#include <vector>
#include <iterator>
#include <cstdlib>
#include <algorithm>
using std::vector;
using std::cout;

int count;
int cc=0;//in the recursive count
int cr=0;//recursive count
const static int TOTAL=8;

void printQi(vector<int> &v){
	cout<<"\n================begin===============\n";
	for(int i=0;i<TOTAL;i++){
		for(int j=0;j<TOTAL;j++){
			if(j==v[i]){
				cout<<"-"<<v[i]<<"-";
			}else{
				cout<<"---";
			}
		}
		cout<<"\n";
	}
	
	cout<<count<<"================end===============\n";
}

//if last one not in column /row /slash with previous
bool checkok(vector<int> &v){
	//cout<<"check visited:"<<v.size()<<"\n";
	//std::copy(v.begin(),v.end(),std::ostream_iterator<int>(cout," "));
	
	int vs=v.size();
	if(vs<2)
		return true;
		
	int lastpos=v.size()-1;
	int lastval=v[lastpos];

	for(int i=0;i<lastpos;i++){
		int x=lastpos-i;
		if(x<0)
			x=-1*x;
		int y=lastval-v[i];
		if(y<0)
			y=-1*y;
//		printf("compare %d,%d\n",x,y);
		if(x==0 || y==0 || x==y)
			return false;
	}
	return true;
}

void dumpnums(vector<int> &v,vector<int> &visited){
	cr++;
	if(visited.size()==v.size()){
		std::copy(visited.begin(),visited.end(),std::ostream_iterator<int>(cout," "));
		printQi(visited);
		cout<<" cc is "<<cc<<"\n";
		cout<<" cr is "<<cr<<"\n";
		count++;
		return;
	}
	
	cr++;
	for(int i=0;i<v.size();i++){
		int s=v[i];
		vector<int>::const_iterator it=std::find(visited.begin(),visited.end(),s);
		if(it == visited.end()){			
			visited.push_back(v[i]);
			
			cc++;
			if(checkok(visited))
				dumpnums(v,visited);
			
			vector<int>::iterator nt=std::find(visited.begin(),visited.end(),s);
			visited.erase(nt);
		}
	}
}

int main(){
	
	
	vector<int> v;
	for(int i=0;i<TOTAL;i++){
		v.push_back(i);
	}
	std::copy(v.begin(),v.end(),std::ostream_iterator<int>(cout," "));
	
	vector<int> visited;
	dumpnums(v,visited);
	
	cout<<"\n"<<"total:"<<count<<"\n";
	
	vector<int> vv;
	vv.push_back(4);
	vv.push_back(3);
	if(checkok(vv)){
		printf("ok");
	}else{
		printf("not ok");
	}
}